{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "textbook_algos_hands_on_pub.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "GbFgwEIW83qL",
        "vum44toJd_bb",
        "QbpYdr9Ngoyq",
        "96A0m3YUZ8D9",
        "5cf9gaXCpmq4",
        "pnddp79QmZAl"
      ],
      "include_colab_link": true
    },
    "kernelspec": {
      "display_name": "Python [default]",
      "language": "python",
      "name": "python3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/JackHidary/quantumcomputingbook/blob/master/Notes/textbook_algos_hands_on_pub.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lORoela1QICx",
        "colab_type": "text"
      },
      "source": [
        "# Textbook Algorithms in Cirq\n",
        "\n",
        "In this notebook we'll run through some Cirq implementations of some of the standard algorithms that one encounters in an introductory quantum computing course. The discussion here is expanded from examples found in the [Cirq examples](https://github.com/quantumlib/Cirq/tree/master/examples) directory.\n",
        "\n",
        "## Instructions\n",
        "\n",
        "Go to File --> Save Copy in Drive to get your own copy to play with.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pPMSHs4HQfSR",
        "colab_type": "code",
        "outputId": "d669a45b-3e7a-49f0-eaa5-15fd2b67b060",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 71
        }
      },
      "source": [
        "# install cirq\n",
        "!pip install cirq==0.5 --quiet"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "\u001b[K     |████████████████████████████████| 716kB 2.7MB/s \n",
            "\u001b[K     |████████████████████████████████| 12.8MB 45.0MB/s \n",
            "\u001b[31mERROR: albumentations 0.1.12 has requirement imgaug<0.2.7,>=0.2.5, but you'll have imgaug 0.2.9 which is incompatible.\u001b[0m\n",
            "\u001b[?25h"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GPjUqrK8DJTq",
        "colab_type": "text"
      },
      "source": [
        "To verify that Cirq is installed in your environment, try to `import cirq` and print out a diagram of the Bristlecone device."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FTrmLyq4C2gf",
        "colab_type": "code",
        "outputId": "e0940115-9909-459b-8417-1b6f78bd7b01",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 575
        }
      },
      "source": [
        "import cirq\n",
        "import numpy as np\n",
        "import random\n",
        "\n",
        "print(cirq.google.Bristlecone)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "                                             (0, 5)────(0, 6)\n",
            "                                             │         │\n",
            "                                             │         │\n",
            "                                    (1, 4)───(1, 5)────(1, 6)────(1, 7)\n",
            "                                    │        │         │         │\n",
            "                                    │        │         │         │\n",
            "                           (2, 3)───(2, 4)───(2, 5)────(2, 6)────(2, 7)───(2, 8)\n",
            "                           │        │        │         │         │        │\n",
            "                           │        │        │         │         │        │\n",
            "                  (3, 2)───(3, 3)───(3, 4)───(3, 5)────(3, 6)────(3, 7)───(3, 8)───(3, 9)\n",
            "                  │        │        │        │         │         │        │        │\n",
            "                  │        │        │        │         │         │        │        │\n",
            "         (4, 1)───(4, 2)───(4, 3)───(4, 4)───(4, 5)────(4, 6)────(4, 7)───(4, 8)───(4, 9)───(4, 10)\n",
            "         │        │        │        │        │         │         │        │        │        │\n",
            "         │        │        │        │        │         │         │        │        │        │\n",
            "(5, 0)───(5, 1)───(5, 2)───(5, 3)───(5, 4)───(5, 5)────(5, 6)────(5, 7)───(5, 8)───(5, 9)───(5, 10)───(5, 11)\n",
            "         │        │        │        │        │         │         │        │        │        │\n",
            "         │        │        │        │        │         │         │        │        │        │\n",
            "         (6, 1)───(6, 2)───(6, 3)───(6, 4)───(6, 5)────(6, 6)────(6, 7)───(6, 8)───(6, 9)───(6, 10)\n",
            "                  │        │        │        │         │         │        │        │\n",
            "                  │        │        │        │         │         │        │        │\n",
            "                  (7, 2)───(7, 3)───(7, 4)───(7, 5)────(7, 6)────(7, 7)───(7, 8)───(7, 9)\n",
            "                           │        │        │         │         │        │\n",
            "                           │        │        │         │         │        │\n",
            "                           (8, 3)───(8, 4)───(8, 5)────(8, 6)────(8, 7)───(8, 8)\n",
            "                                    │        │         │         │\n",
            "                                    │        │         │         │\n",
            "                                    (9, 4)───(9, 5)────(9, 6)────(9, 7)\n",
            "                                             │         │\n",
            "                                             │         │\n",
            "                                             (10, 5)───(10, 6)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "laCvAwThaADq",
        "colab_type": "text"
      },
      "source": [
        "## Quantum Teleportation"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xytEjvt9cD5L",
        "colab_type": "text"
      },
      "source": [
        "Quantum Teleportation is a process by which a quantum state can be transmitted\n",
        "by sending only two classical bits of information. This is accomplished by\n",
        "pre-sharing an entangled state between the sender (Alice) and the receiver\n",
        "(Bob). This entangled state allows the receiver (Bob) of the two classical\n",
        "bits of information to possess a qubit with the same state as the one held by\n",
        "the sender (Alice).\n",
        "In the following example output, qubit 0 (the Message) is set to a random state\n",
        "by applying X and Y gates. By sending two classical bits of information after\n",
        "qubit 0 (the Message) and qubit 1 (Alice's entangled qubit) are measured, the\n",
        "final state of qubit 2 (Bob's entangled qubit) will be identical to the\n",
        "original random state of qubit 0 (the Message). This is only possible given\n",
        "that an entangled state is pre-shared between Alice and Bob.\n",
        "\n",
        "=== REFERENCES ===\n",
        "\n",
        "https://en.wikipedia.org/wiki/Quantum_teleportation\n",
        "https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.70.1895"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ex8ka640a5xN",
        "colab_type": "code",
        "outputId": "d502f89a-beee-46d7-c341-164606fefcad",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 251
        }
      },
      "source": [
        "def make_quantum_teleportation_circuit(gate):\n",
        "    circuit = cirq.Circuit()\n",
        "    msg, alice, bob = cirq.LineQubit.range(3)\n",
        "\n",
        "    # Creates Bell state to be shared between Alice and Bob\n",
        "    circuit.append([cirq.H(alice), cirq.CNOT(alice, bob)])\n",
        "    # Creates a random state for the Message\n",
        "    circuit.append(gate(msg))\n",
        "    # Bell measurement of the Message and Alice's entangled qubit\n",
        "    circuit.append([cirq.CNOT(msg, alice), cirq.H(msg)])\n",
        "    circuit.append(cirq.measure(msg, alice))\n",
        "    # Uses the two classical bits from the Bell measurement to recover the\n",
        "    # original quantum Message on Bob's entangled qubit\n",
        "    circuit.append([cirq.CNOT(alice, bob), cirq.CZ(msg, bob)])\n",
        "\n",
        "    return circuit\n",
        "\n",
        "\n",
        "gate = cirq.SingleQubitMatrixGate(cirq.testing.random_unitary(2))\n",
        "circuit = make_quantum_teleportation_circuit(gate)\n",
        "\n",
        "print(\"Circuit:\")\n",
        "print(circuit)\n",
        "\n",
        "sim = cirq.Simulator()\n",
        "\n",
        "# Create qubits.\n",
        "q0 = cirq.LineQubit\n",
        "\n",
        "# Produces the message using random unitary\n",
        "message = sim.simulate(cirq.Circuit.from_ops(gate(q0)))\n",
        "\n",
        "print(\"Bloch Vector of Message After Random Unitary:\")\n",
        "# Prints the Bloch vector of the Message after the random gate\n",
        "b0X, b0Y, b0Z = cirq.bloch_vector_from_state_vector(\n",
        "    message.final_state, 0)\n",
        "print(\"x: \", np.around(b0X, 4),\n",
        "      \"y: \", np.around(b0Y, 4),\n",
        "      \"z: \", np.around(b0Z, 4))\n",
        "\n",
        "# Records the final state of the simulation\n",
        "final_results = sim.simulate(circuit)\n",
        "\n",
        "print(\"Bloch Sphere of Qubit 2 at Final State:\")\n",
        "# Prints the Bloch Sphere of Bob's entangled qubit at the final state\n",
        "b2X, b2Y, b2Z = cirq.bloch_vector_from_state_vector(\n",
        "    final_results.final_state, 2)\n",
        "print(\"x: \", np.around(b2X, 4),\n",
        "      \"y: \", np.around(b2Y, 4),\n",
        "      \"z: \", np.around(b2Z, 4))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Circuit:\n",
            "      ┌                         ┐\n",
            "0: ───│0.23 +0.039j 0.146+0.961j│───────@───H───M───────@───\n",
            "      │0.405+0.884j 0.171-0.159j│       │       │       │\n",
            "      └                         ┘       │       │       │\n",
            "                                        │       │       │\n",
            "1: ───H─────────────────────────────@───X───────M───@───┼───\n",
            "                                    │               │   │\n",
            "2: ─────────────────────────────────X───────────────X───@───\n",
            "Bloch Vector of Message After Random Unitary:\n",
            "x:  0.2552 y:  0.3752 z:  -0.8911\n",
            "Bloch Sphere of Qubit 2 at Final State:\n",
            "x:  0.2552 y:  0.3752 z:  -0.8911\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9tshDM1XaKA3",
        "colab_type": "text"
      },
      "source": [
        "## Deutsch's Algorithm\n",
        "\n",
        "Deutsch's algorithm is one of the simplest demonstrations of quantum parallelism\n",
        "and interference. It takes a black-box oracle implementing a Boolean function\n",
        "f(x), and determines whether f(0) and f(1) have the same parity using just one\n",
        "query.  This version of Deutsch's algorithm is a simplified and improved version\n",
        "from Nielsen and Chuang's textbook.\n",
        "\n",
        "=== REFERENCE ===\n",
        "\n",
        "https://en.wikipedia.org/wiki/Deutsch–Jozsa_algorithm\n",
        "Deutsch, David. \"Quantum theory, the Church-Turing Principle and the universal\n",
        "quantum computer.\" Proc. R. Soc. Lond. A, 400:97, 1985."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QNxWksLhe-Kv",
        "colab_type": "code",
        "outputId": "6e717e18-13fa-4d81-89a8-085eb402b389",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 161
        }
      },
      "source": [
        "def make_oracle(q0, q1, secret_function):\n",
        "    \"\"\" Gates implementing the secret function f(x).\"\"\"\n",
        "\n",
        "    # coverage: ignore\n",
        "    if secret_function[0]:\n",
        "        yield [cirq.CNOT(q0, q1), cirq.X(q1)]\n",
        "\n",
        "    if secret_function[1]:\n",
        "        yield cirq.CNOT(q0, q1)\n",
        "\n",
        "\n",
        "def make_deutsch_circuit(q0, q1, oracle):\n",
        "    c = cirq.Circuit()\n",
        "\n",
        "    # Initialize qubits.\n",
        "    c.append([cirq.X(q1), cirq.H(q1), cirq.H(q0)])\n",
        "\n",
        "    # Query oracle.\n",
        "    c.append(oracle)\n",
        "\n",
        "    # Measure in X basis.\n",
        "    c.append([cirq.H(q0), cirq.measure(q0, key='result')])\n",
        "    return c\n",
        "  \n",
        "# Choose qubits to use.\n",
        "q0, q1 = cirq.LineQubit.range(2)\n",
        "\n",
        "# Pick a secret 2-bit function and create a circuit to query the oracle.\n",
        "secret_function = [random.randint(0,1) for _ in range(2)]\n",
        "oracle = make_oracle(q0, q1, secret_function)\n",
        "print('Secret function:\\nf(x) = <{}>'.format(\n",
        "    ', '.join(str(e) for e in secret_function)))\n",
        "\n",
        "# Embed the oracle into a quantum circuit querying it exactly once.\n",
        "circuit = make_deutsch_circuit(q0, q1, oracle)\n",
        "print('Circuit:')\n",
        "print(circuit)\n",
        "\n",
        "# Simulate the circuit.\n",
        "simulator = cirq.Simulator()\n",
        "result = simulator.run(circuit)\n",
        "print('Result of f(0)⊕f(1):')\n",
        "print(result)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Secret function:\n",
            "f(x) = <0, 0>\n",
            "Circuit:\n",
            "0: ───H───H───M('result')───\n",
            "\n",
            "1: ───X───H─────────────────\n",
            "Result of f(0)⊕f(1):\n",
            "result=0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LHcyAAtbQBdM",
        "colab_type": "text"
      },
      "source": [
        "## Quantum Fourier Transform and Phase Estimation\n",
        "\n",
        "This section provides an overview of the quantum Fourier transform and its use in the Phase Estimation algorithm in Cirq."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wTQFlM356vQG",
        "colab_type": "text"
      },
      "source": [
        "### Quantum Fourier Transform: Overview\n",
        "\n",
        "We'll start out by reminding ourselves what the [quantum Fourier transform](https://en.wikipedia.org/wiki/Quantum_Fourier_transform) does, and how it should be constructed."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EKi8ZKeOI8MX",
        "colab_type": "text"
      },
      "source": [
        "Suppose we have $n$ qubits in the state $|x\\rangle$, where $x$ is an integer in the range $0$ to $2^{n-1}$. The quantum Fourier transform (QFT) performs the following operation:\n",
        "$$\n",
        "\\text{QFT}|x\\rangle = \\frac{1}{2^{n/2}} \\sum_{y=0}^{2^n-1} e^{2\\pi i y x/2^n} |y\\rangle.\n",
        "$$\n",
        "When $x=0$, this is the same as the action of $H^{\\otimes n}$ (this is an important sanity check). Though it may not be obvious at first glance, the QFT is actually a unitary transformation. As a matrix, the QFT is given by\n",
        "$$\n",
        "\\text{QFT} = \\begin{bmatrix}\n",
        "1 & 1 & 1& \\cdots &1 \\\\\n",
        "1 & \\omega & \\omega^2& \\cdots &\\omega^{2^n-1} \\\\\n",
        "1 & \\omega^2 & \\omega^4& \\cdots &\\omega^{2(2^n-1)}\\\\\n",
        "\\vdots &\\vdots &\\vdots &\\ddots &\\vdots \\\\\n",
        "1 &\\omega^{2^n-1} &\\omega^{2(2^n-1)} &\\cdots &\\omega^{(2^n-1)(2^n-1)},\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "where $\\omega = e^{2\\pi i /2^n}$. If you believe that the QFT is unitary, then you'll also notice from the matrix form that its inverse is given by a similar expression but with complex-conjugated coefficients:\n",
        "$$\n",
        "\\text{QFT}^{-1}|x\\rangle = \\frac{1}{2^{n/2}} \\sum_{y=0}^{2^n-1} e^{-2\\pi i y x/2^n} |y\\rangle.\n",
        "$$"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xyhgCosQK3j4",
        "colab_type": "text"
      },
      "source": [
        "The construction of the QFT as a circuit follows a simple recursive form, though fully justifying it will take us too far from the main goal of this notebook. We really only need to know what the circuit looks like, and for that we can look at this picture from the Wikipedia article:\n",
        "\n",
        ">![QFT Circuit](https://upload.wikimedia.org/wikipedia/commons/6/61/Q_fourier_nqubits.png)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "q3fIRQhv6LVp",
        "colab_type": "text"
      },
      "source": [
        "We just need to understand the notation a little bit. $x_j$ on the left-hand side represents one of the binary digits of the input $x$. $x_1$ is the most significant bit and $x_n$ the least significant bit:\n",
        "$$\n",
        "x = \\sum_{j=0}^{n-1} x_{j+1}2^j.\n",
        "$$\n",
        "$H$ is the Hadamard gate, as usual. The Controlled-$R_j$ gates are phase gates similar to the Controlled-$Z$ gate. In fact, for us it will be useful to just think of them as fractional powers of Controlled-$Z$ gates:\n",
        "$$\n",
        "CR_j = CZ^{\\large 1/2^{j-1}}\n",
        "$$\n",
        "Finally, on the far right we have the output representing the bts of $y$. The only difference between the left and right side is that the output bits are in a different order: the most significant bit of $y$ is on the bottom and the least significant bit is on the top."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2dyP_y5AGcWP",
        "colab_type": "text"
      },
      "source": [
        "### Quantum Fourier Transform as a Circuit"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RJhjgemX8QXe",
        "colab_type": "text"
      },
      "source": [
        "Let's define a generator which produces the QFT circuit. It should accept a list of qubits as input and `yield`s the gates to construct the QFT in the right order. A useful observation is that the the QFT circuit \"repeats\" smaller versions of itself as you move from left to right across the diagram."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Fu0wP9sLG94Z",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def make_qft(qubits):\n",
        "  \"\"\"Generator for the QFT on an arbitrary number of qubits. With four qubits\n",
        "  the answer is\n",
        "  ---H--@-------@--------@---------------------------------------------\n",
        "        |       |        |\n",
        "  ------@^0.5---+--------+---------H--@-------@------------------------\n",
        "                |        |            |       |\n",
        "  --------------@^0.25---+------------@^0.5---+---------H--@-----------\n",
        "                         |                    |            |\n",
        "  -----------------------@^0.125--------------@^0.25-------@^0.5---H---\n",
        "  \"\"\"\n",
        "  # YOUR CODE HERE"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GbFgwEIW83qL",
        "colab_type": "text"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CtDX3krz87eC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def make_qft(qubits):\n",
        "  \"\"\"Generator for the QFT on an arbitrary number of qubits. With four qubits\n",
        "  the answer is\n",
        "  ---H--@-------@--------@---------------------------------------------\n",
        "        |       |        |\n",
        "  ------@^0.5---+--------+---------H--@-------@------------------------\n",
        "                |        |            |       |\n",
        "  --------------@^0.25---+------------@^0.5---+---------H--@-----------\n",
        "                         |                    |            |\n",
        "  -----------------------@^0.125--------------@^0.25-------@^0.5---H---\n",
        "  \"\"\"\n",
        "  qubits = list(qubits)\n",
        "  while len(qubits) > 0:\n",
        "      q_head = qubits.pop(0)\n",
        "      yield cirq.H(q_head)\n",
        "      for i, qubit in enumerate(qubits):\n",
        "          yield (cirq.CZ**(1/2**(i+1)))(qubit, q_head)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nhbBPpf9GiHO",
        "colab_type": "code",
        "outputId": "b05c4142-1b9b-4852-d27c-c26959b2befa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 179
        }
      },
      "source": [
        "num_qubits = 4\n",
        "qubits = cirq.LineQubit.range(num_qubits)\n",
        "\n",
        "qft = cirq.Circuit.from_ops(make_qft(qubits))\n",
        "print(qft)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "                  ┌───────┐   ┌────────────┐   ┌───────┐\n",
            "0: ───H───@────────@───────────@───────────────────────────────────────\n",
            "          │        │           │\n",
            "1: ───────@^0.5────┼─────H─────┼──────@─────────@──────────────────────\n",
            "                   │           │      │         │\n",
            "2: ────────────────@^0.25──────┼──────@^0.5─────┼─────H────@───────────\n",
            "                               │                │          │\n",
            "3: ────────────────────────────@^(1/8)──────────@^0.25─────@^0.5───H───\n",
            "                  └───────┘   └────────────┘   └───────┘\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uaDb6B_jPgrb",
        "colab_type": "text"
      },
      "source": [
        "### Quantum Fourier Transform as a Gate\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2CASB7V2dZt3",
        "colab_type": "text"
      },
      "source": [
        "For later convenience, it will be useful to encapsulate the QFT construction into a single gate. We can inherit from  `cirq.Gate` to define a gate which acts on an unspecified number of qubits, and then use the same strategy as for `make_qft` in the `_decompose_` method of the gate. Fill in the following code block to make a QFT gate."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Yi-CcZFyeh39",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class QFT(cirq.Gate):\n",
        "  \"\"\"Gate for the Quantum Fourier Transformation\n",
        "  \"\"\"\n",
        "  \n",
        "  def __init__(self, n_qubits):\n",
        "    self.n_qubits = n_qubits\n",
        "\n",
        "  def num_qubits(self):\n",
        "    return self.n_qubits    \n",
        "    \n",
        "  def _decompose_(self, qubits):\n",
        "    # YOUR CODE HERE\n",
        "            \n",
        "  # How should the gate look in ASCII diagrams?          \n",
        "  def _circuit_diagram_info_(self, args):        \n",
        "    return tuple('QFT{}'.format(i) for i in range(self.n_qubits))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vum44toJd_bb",
        "colab_type": "text"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7Jkk8dnaiFzF",
        "colab_type": "text"
      },
      "source": [
        "A copy/paste is all that's required here:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3AmLWwEuCXP8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class QFT(cirq.Gate):\n",
        "  \"\"\"Gate for the Quantum Fourier Transformation\n",
        "  \"\"\"\n",
        "  \n",
        "  def __init__(self, n_qubits):\n",
        "    self.n_qubits = n_qubits\n",
        "\n",
        "  def num_qubits(self):\n",
        "    return self.n_qubits\n",
        "    \n",
        "  def _decompose_(self, qubits):\n",
        "    \"\"\"Implements the QFT on an arbitrary number of qubits. The circuit\n",
        "    for num_qubits = 4 is given by\n",
        "    ---H--@-------@--------@---------------------------------------------\n",
        "          |       |        |\n",
        "    ------@^0.5---+--------+---------H--@-------@------------------------\n",
        "                  |        |            |       |\n",
        "    --------------@^0.25---+------------@^0.5---+---------H--@-----------\n",
        "                           |                    |            |\n",
        "    -----------------------@^0.125--------------@^0.25-------@^0.5---H---\n",
        "    \"\"\"\n",
        "    qubits = list(qubits)\n",
        "    while len(qubits) > 0:\n",
        "        q_head = qubits.pop(0)\n",
        "        yield cirq.H(q_head)\n",
        "        for i, qubit in enumerate(qubits):\n",
        "            yield (cirq.CZ**(1/2**(i+1)))(qubit, q_head)\n",
        "            \n",
        "  # How should the gate look in ASCII diagrams?          \n",
        "  def _circuit_diagram_info_(self, args):        \n",
        "    return tuple('QFT{}'.format(i) for i in range(self.n_qubits))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L9dMWuwqewjc",
        "colab_type": "text"
      },
      "source": [
        "#### Test the Circuit"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HgYjV70FfnDr",
        "colab_type": "text"
      },
      "source": [
        "We should confirm that the gate we've defined is actually doing the same thing as the `make_qft` function from before. We can do that with the following test:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "i3Ir6kjmDqtt",
        "colab_type": "code",
        "outputId": "bbce11cc-1599-4a1a-e41a-205082401705",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 305
        }
      },
      "source": [
        "num_qubits = 4\n",
        "\n",
        "qubits = cirq.LineQubit.range(num_qubits)\n",
        "circuit = cirq.Circuit.from_ops(QFT(num_qubits).on(*qubits))\n",
        "print(circuit)\n",
        "\n",
        "qft_test = cirq.Circuit.from_ops(make_qft(qubits))\n",
        "print(qft_test)\n",
        "np.testing.assert_allclose(cirq.unitary(qft_test), cirq.unitary(circuit))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0: ───QFT0───\n",
            "      │\n",
            "1: ───QFT1───\n",
            "      │\n",
            "2: ───QFT2───\n",
            "      │\n",
            "3: ───QFT3───\n",
            "                  ┌───────┐   ┌────────────┐   ┌───────┐\n",
            "0: ───H───@────────@───────────@───────────────────────────────────────\n",
            "          │        │           │\n",
            "1: ───────@^0.5────┼─────H─────┼──────@─────────@──────────────────────\n",
            "                   │           │      │         │\n",
            "2: ────────────────@^0.25──────┼──────@^0.5─────┼─────H────@───────────\n",
            "                               │                │          │\n",
            "3: ────────────────────────────@^(1/8)──────────@^0.25─────@^0.5───H───\n",
            "                  └───────┘   └────────────┘   └───────┘\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "grSAE3QKf6JB",
        "colab_type": "text"
      },
      "source": [
        "#### Inverse QFT\n",
        "\n",
        "We also want to implement the inverse QFT, which we'll do with a completely separate gate. Modify the `QFT` gate from above to create a `QFT_inv` gate:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pdMBeOhxgnA7",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class QFT_inv(cirq.Gate):\n",
        "  \"\"\"Gate for the inverse Quantum Fourier Transformation\n",
        "  \"\"\"\n",
        "  \n",
        "  # YOUR CODE HERE"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QbpYdr9Ngoyq",
        "colab_type": "text"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v8xOsr6limAI",
        "colab_type": "text"
      },
      "source": [
        "Compared to the `QFT` code above, we just have to add in a few minus signs. You can convince yourself that this is the same as complex-conjugating the associated unitary matrix of the QFT, which gives us the inverse QFT."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bOw5cWIJM8aU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class QFT_inv(cirq.Gate):\n",
        "  \"\"\"Gate for the inverse Quantum Fourier Transformation\n",
        "  \"\"\"\n",
        "  \n",
        "  def __init__(self, n_qubits):\n",
        "    self.n_qubits = n_qubits\n",
        "\n",
        "  def num_qubits(self):\n",
        "    return self.n_qubits   \n",
        "    \n",
        "  def _decompose_(self, qubits):\n",
        "    \"\"\"Implements the inverse QFT on an arbitrary number of qubits. The circuit\n",
        "    for num_qubits = 4 is given by\n",
        "    ---H--@-------@--------@---------------------------------------------\n",
        "          |       |        |\n",
        "    ------@^-0.5--+--------+---------H--@-------@------------------------\n",
        "                  |        |            |       |\n",
        "    --------------@^-0.25--+------------@^-0.5--+---------H--@-----------\n",
        "                           |                    |            |\n",
        "    -----------------------@^-0.125-------------@^-0.25------@^-0.5--H---\n",
        "    \"\"\"\n",
        "    qubits = list(qubits)\n",
        "    while len(qubits) > 0:\n",
        "        q_head = qubits.pop(0)\n",
        "        yield cirq.H(q_head)\n",
        "        for i, qubit in enumerate(qubits):\n",
        "            yield (cirq.CZ**(-1/2**(i+1)))(qubit, q_head)\n",
        "                      \n",
        "  def _circuit_diagram_info_(self, args):        \n",
        "    return tuple('QFT{}^-1'.format(i) for i in range(self.n_qubits))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ql8uuojrZYIb",
        "colab_type": "text"
      },
      "source": [
        "#### Is the QFT_inv gate the inverse of the QFT Circuit?\n",
        "\n",
        "We chose not to define the `QFT_inv` as literally the inverse of the `QFT` gate. Why was that? What would you get if you concetenated the `QFT` and `QFT_inv` gates as defined? (Try it!) Can you put together `QFT` and `QFT_inv` in such a way that one undoes the action of the other? This exercise doubles as a test of the `QFT_inv` implementation."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "96A0m3YUZ8D9",
        "colab_type": "text"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oIGLoN1ZZ-FF",
        "colab_type": "text"
      },
      "source": [
        "The QFT and QFT_inv circuits we have defined are not literal inverses of each other because the both reverse the order of the bits when going from input to output. We can explicitly see this in the following code block:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dN-3VfHIaNIb",
        "colab_type": "code",
        "outputId": "556ea306-1725-4e59-eb95-667fd3ad3816",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 143
        }
      },
      "source": [
        "num_qubits = 2\n",
        "\n",
        "qubits = cirq.LineQubit.range(num_qubits)\n",
        "circuit = cirq.Circuit.from_ops(QFT(num_qubits).on(*qubits),\n",
        "                                QFT_inv(num_qubits).on(*qubits))\n",
        "print(circuit)\n",
        "cirq.unitary(circuit).round(2)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0: ───QFT0───QFT0^-1───\n",
            "      │      │\n",
            "1: ───QFT1───QFT1^-1───\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1. +0.j , 0. +0.j , 0. +0.j , 0. +0.j ],\n",
              "       [0. +0.j , 0.5+0.5j, 0. +0.j , 0.5-0.5j],\n",
              "       [0. +0.j , 0.5+0.j , 0.5-0.5j, 0. +0.5j],\n",
              "       [0. +0.j , 0. -0.5j, 0.5+0.5j, 0.5+0.j ]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 41
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gzCrlfiyacUB",
        "colab_type": "text"
      },
      "source": [
        "If `QFT` and `QFT_inv` were really inverses then we would have gotten the identity matrix here. There are a couple of ways to fix this. One is to change the implementations of these two gates in such a way that the outputs are \"rightside-up.\" A different solution is to turn the qubits around in between acting with `QFT` and `QFT_inv`. In other words, we can insert the `QFT_inv` gate \"upside-down\" as follows:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vbAFFR8kbJsk",
        "colab_type": "code",
        "outputId": "9096b2ee-92da-48ac-b4b9-77d818792623",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 143
        }
      },
      "source": [
        "num_qubits = 2\n",
        "\n",
        "qubits = cirq.LineQubit.range(num_qubits)\n",
        "circuit = cirq.Circuit.from_ops(QFT(num_qubits).on(*qubits),\n",
        "                                QFT_inv(num_qubits).on(*qubits[::-1])) # qubit order reversed\n",
        "print(circuit)\n",
        "cirq.unitary(circuit)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0: ───QFT0───QFT1^-1───\n",
            "      │      │\n",
            "1: ───QFT1───QFT0^-1───\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[1.+0.j, 0.+0.j, 0.+0.j, 0.+0.j],\n",
              "       [0.+0.j, 1.+0.j, 0.+0.j, 0.+0.j],\n",
              "       [0.+0.j, 0.+0.j, 1.+0.j, 0.+0.j],\n",
              "       [0.+0.j, 0.+0.j, 0.+0.j, 1.+0.j]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 44
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Njo9x-H9cZ4K",
        "colab_type": "text"
      },
      "source": [
        "We find the identity matrix, as desired (up to finite-precision numerical errors). Notice that the `QFT_inv` gate is upside-down relative to the `QFT` gate in the diagram. This is why we included the extra digits in the `wire_symobls`!"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "r-CjbPwkRI_I",
        "colab_type": "text"
      },
      "source": [
        "### Phase Estimation\n",
        "\n",
        "As an application of our quantum Fourier transform circuit, we'll implement the [phase estimation](https://en.wikipedia.org/wiki/Quantum_phase_estimation_algorithm) algorithm. The phase estimation algorithm uses the inverse QFT to give an estimate of the eigenvalue of a unitary operator. The total circuit that we are going to implement is given by"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "gJ01TOhr4CQN",
        "colab_type": "text"
      },
      "source": [
        ">![Phase Estimation](https://upload.wikimedia.org/wikipedia/commons/a/a5/PhaseCircuit-crop.svg)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "_15iEUy5Rk1o",
        "colab_type": "text"
      },
      "source": [
        "Suppose we have a unitary operator $U$ with eigenvactor $|\\psi\\rangle$ and eigenvalue $\\exp(2\\pi i \\theta)$. Our objective is to get an $n$-bit approximation to $\\theta$. The first step is to construct the state\n",
        "$$\n",
        "|\\Phi\\rangle = \\frac{1}{2^{n/2}}\\sum_{y=0}^{2^{n-1}} e^{2\\pi i y \\theta}|y\\rangle.\n",
        "$$\n",
        "This looks very similar to the output of the QFT applied to the state $|2^n\\theta\\rangle$, except for the fact that $2^n\\theta$ may not be an integer. If $2^n\\theta$ *were* an integer, then we would apply the inverse QFT and measure the qubits to read off the binary representation of $2^n\\theta$. Even if $2^n\\theta$ is not an integer, we can still perform the same procedure and the result will be a sequence of bits that, with high probility, gives an $n$-bit approximation to $\\theta$. We just have to repeat the procedure a few times to be sure of the answer."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "sypcpUzLTxRK",
        "colab_type": "text"
      },
      "source": [
        "Since we've already constructed the inverse QFT, all we really have to do is figure out how to construct the magic state $|\\Phi\\rangle$. This is accomplished by the first part of the circuit picutred above. We begin by applying $H^{\\otimes n}$ to the state $|0\\rangle$, creating an equal superposition over all basis states:\n",
        "$$\n",
        "H^{\\otimes n} |0\\rangle = \\frac{1}{2^{n/2}}\\sum_{y=0}^{2^n-1}|y\\rangle.\n",
        "$$\n",
        "Now we need to insert the correct phase coefficients. This is done by a sequence of Controlled-$U^k$ operations, where the qubits of $y$ are the controls and the $U^k$ operations act on $|\\psi \\rangle$.\n",
        "\n",
        "Let's try to implement this part of the procedure in Cirq, and then put it together with our `QFT_inv` from above. For the gate $U$ we'll pick the single-qubit operation\n",
        "$$\n",
        "U = Z^{2\\theta} = \\begin{bmatrix}\n",
        "1 & 0 \\\\\n",
        "0 & e^{2\\pi i \\theta }\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "for $\\theta \\in [0,1)$. This is just for simplicity and ease of testing. You are invited to write an implementation that accepts an arbitrary $U$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OIN8QfUeJyI9",
        "colab_type": "code",
        "outputId": "b77f8a31-ae9a-4486-8a9d-7df0809109a2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 143
        }
      },
      "source": [
        "theta = 0.234 # Try your own\n",
        "n_bits = 3 # Accuracy of the estimate for theta. Try different values.\n",
        "\n",
        "qubits = cirq.LineQubit.range(n_bits)\n",
        "u_bit = cirq.NamedQubit('u')\n",
        "\n",
        "U = cirq.Z**(2*theta)\n",
        "\n",
        "phase_estimator = cirq.Circuit()\n",
        "\n",
        "phase_estimator.append(cirq.H.on_each(*qubits))\n",
        "for i, bit in enumerate(qubits):\n",
        "  phase_estimator.append(cirq.ControlledGate(U).on(bit,u_bit)**(2**(n_bits-1-i)))\n",
        "\n",
        "print(phase_estimator)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0: ───H───@──────────────────────────────\n",
            "          │\n",
            "1: ───H───┼──────────@───────────────────\n",
            "          │          │\n",
            "2: ───H───┼──────────┼─────────@─────────\n",
            "          │          │         │\n",
            "u: ───────Z^-0.128───Z^0.936───Z^0.468───\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QTVJnv8Yx5bm",
        "colab_type": "text"
      },
      "source": [
        "The next step is to perform the inverse QFT on estimation qubits:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8KCn-gjxM2H9",
        "colab_type": "code",
        "outputId": "58a87b3c-8872-47ec-d404-97e2e83d98bc",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 143
        }
      },
      "source": [
        "phase_estimator.append(QFT_inv(n_bits).on(*qubits))\n",
        "print(phase_estimator)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0: ───H───@──────────────────────────────QFT0^-1───\n",
            "          │                              │\n",
            "1: ───H───┼──────────@───────────────────QFT1^-1───\n",
            "          │          │                   │\n",
            "2: ───H───┼──────────┼─────────@─────────QFT2^-1───\n",
            "          │          │         │\n",
            "u: ───────Z^-0.128───Z^0.936───Z^0.468─────────────\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "smlXIG1QyPyR",
        "colab_type": "text"
      },
      "source": [
        "At this point we are almost ready to measure the estimation qubits. But we should also specify an initial state for the `u_bit`. By default it will be the state $|0\\rangle$, but the phase for that state is trivial with the operator we chose. Inserting a Pauli $X$ operator at the begining of the circuit changes this to the $|1\\rangle$ state, which has the nontrivial $\\theta$ phase. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "g_rNMrkXPJ0R",
        "colab_type": "code",
        "outputId": "b490330c-16d2-45ea-abff-e5bdac59da5a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 143
        }
      },
      "source": [
        "# Add measurements to the end of the circuit\n",
        "phase_estimator.append(cirq.measure(*qubits, key='m'))\n",
        "\n",
        "# Add gate to change initial state to |1>\n",
        "phase_estimator.insert(0,cirq.X(u_bit))\n",
        "\n",
        "print(phase_estimator)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0: ───H───@──────────────────────────────QFT0^-1───M('m')───\n",
            "          │                              │         │\n",
            "1: ───H───┼──────────@───────────────────QFT1^-1───M────────\n",
            "          │          │                   │         │\n",
            "2: ───H───┼──────────┼─────────@─────────QFT2^-1───M────────\n",
            "          │          │         │\n",
            "u: ───X───Z^-0.128───Z^0.936───Z^0.468──────────────────────\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "j2HIBKbEy7gV",
        "colab_type": "text"
      },
      "source": [
        "Now we can intstantiate a simulator and make measurements of the estimation qubits. Let the values of these qubits be $a_j$. Then our $n$-bit approximation for $\\theta$ is given by\n",
        "$$\n",
        "\\theta \\approx \\sum_{j=0}^n a_j2^{-j}.\n",
        "$$\n",
        "We'll perform this conversion from bit values to $\\theta$-values and then print the results:"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-pE7CC_uPfq2",
        "colab_type": "code",
        "outputId": "dd35ad7d-aab5-4b22-8580-ee9eb03dba4d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "sim = cirq.Simulator()\n",
        "result = sim.run(phase_estimator, repetitions=10)\n",
        "\n",
        "theta_estimates = np.sum(2**np.arange(n_bits)*result.measurements['m'], axis=1)/2**n_bits\n",
        "print(theta_estimates)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25 0.25]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PMke93CrzezN",
        "colab_type": "text"
      },
      "source": [
        "When `n_bits` is small, we don't get a very accurate estimate. You can go back and increase `n_bits` and rerun the cells if you like."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Dn9j1RCrpCj_",
        "colab_type": "text"
      },
      "source": [
        "To make experimentation easier, let's pack all this up into a single function that lets us specify $\\theta$, the number of bits of of accuracy we want in our approxmation, and the number of repetitions of the algorithm to perform. You could just copy/paste from the previous cells, but it might be a useful exercise to write the whole thing from scratch without peeking."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "t3EYxglfpgbh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def phase_estimation(theta, n_bits, n_reps=10):\n",
        "\n",
        "  # YOUR CODE HERE\n",
        "  \n",
        "  return theta_estimates"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5cf9gaXCpmq4",
        "colab_type": "text"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fC5oUxNtppVo",
        "colab_type": "text"
      },
      "source": [
        "Here is a solution that just consists of what we did in previous cells all put together."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TXxJ_ZjeWFqy",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def phase_estimation(theta, n_bits, n_reps=10):\n",
        "  qubits = cirq.LineQubit.range(n_bits)\n",
        "  u_bit = cirq.NamedQubit('u')\n",
        "\n",
        "  U = cirq.Z**(2*theta) # Try out a different gate if you like\n",
        "\n",
        "  phase_estimator = cirq.Circuit()\n",
        "\n",
        "  phase_estimator.append(cirq.H.on_each(*qubits))\n",
        "  for i, bit in enumerate(qubits):\n",
        "    phase_estimator.append(cirq.ControlledGate(U).on(bit,u_bit)**(2**(n_bits-1-i)))\n",
        "  phase_estimator.append(QFT_inv(n_bits).on(*qubits))\n",
        "  \n",
        "  # Measurement gates\n",
        "  phase_estimator.append(cirq.measure(*qubits, key='m'))\n",
        "\n",
        "  # Gates to choose initial state for the u_bit. Placing X here chooses the |1> state\n",
        "  phase_estimator.insert(0,cirq.X(u_bit))\n",
        "\n",
        "  # Code to simulate measurements\n",
        "  sim = cirq.Simulator()\n",
        "  result = sim.run(phase_estimator, repetitions=n_reps)\n",
        "  \n",
        "  # Convert measurements into estimates of theta\n",
        "  theta_estimates = np.sum(2**np.arange(n_bits)*result.measurements['m'], axis=1)/2**n_bits\n",
        "  \n",
        "  return theta_estimates"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "O3otp22NYO2u",
        "colab_type": "code",
        "outputId": "c8ed07e0-7541-4b7a-b121-fdf199aa6a04",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 53
        }
      },
      "source": [
        "phase_estimation(0.234, 10)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([0.234375  , 0.23339844, 0.234375  , 0.23339844, 0.234375  ,\n",
              "       0.23339844, 0.234375  , 0.234375  , 0.23339844, 0.234375  ])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 50
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cr-NVLG2loo7",
        "colab_type": "text"
      },
      "source": [
        "#### Phase Estimation Without an Eigenstate\n",
        "\n",
        "We can modify our `phase_estimation` method to explore other interesting aspects of the algorithm. Suppose the input to the circuit was not an eigenstate of $U$ at all? You could modify the case we analyzed above by putting an arbitrary single-qubit state on the `u_bit`, or you could replace $Z^{2\\theta}$ with something like $X^{2\\theta}$ while still passing in a computational basis state. What is the result?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "pnddp79QmZAl",
        "colab_type": "text"
      },
      "source": [
        "#### Solution"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DTB2pkzWmdS8",
        "colab_type": "text"
      },
      "source": [
        "Suppose the operator $U$ has eigenstate $|u_j\\rangle$ with eigenvalues $e^{2\\pi i \\theta_j}$. Then in general if we pass in a state of the form\n",
        "$$\n",
        "\\sum_j \\alpha_j|u_j\\rangle\n",
        "$$\n",
        "then each time we run the circuit we will get an $n$-bit estimate of one of the $\\theta_j$ chosen at random, and the probability of choosing a particular $\\theta_j$ is given by $|\\alpha_j|^2$. One simple test of this is to modify our above code to pass the state\n",
        "$$\n",
        "\\frac{|0\\rangle + |1\\rangle}{\\sqrt{2}}\n",
        "$$\n",
        "into the phase estimator for $Z^{2\\theta}$. The state $|1\\rangle$ has eigenvalue $e^{2\\pi i \\theta_j}$ while the state $|0\\rangle$ has eigenvalue $1$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kMwW3LFinsX4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def phase_estimation(theta, n_bits, n_reps=10):\n",
        "  qubits = cirq.LineQubit.range(n_bits)\n",
        "  u_bit = cirq.NamedQubit('u')\n",
        "\n",
        "  U = cirq.Z**(2*theta)\n",
        "\n",
        "  phase_estimator = cirq.Circuit()\n",
        "\n",
        "  phase_estimator.append(cirq.H.on_each(*qubits))\n",
        "  for i, bit in enumerate(qubits):\n",
        "    phase_estimator.append(cirq.ControlledGate(U).on(bit,u_bit)**(2**(n_bits-1-i))) # Could have used CZ in this example\n",
        "  phase_estimator.append(QFT_inv(n_bits).on(*qubits))\n",
        "  \n",
        "  phase_estimator.append(cirq.measure(*qubits, key='m'))\n",
        "\n",
        "  # Changed the X gate here to an H\n",
        "  phase_estimator.insert(0,cirq.H(u_bit))\n",
        "\n",
        "  sim = cirq.Simulator()\n",
        "  result = sim.run(phase_estimator, repetitions=n_reps)\n",
        "    \n",
        "  theta_estimates = np.sum(2**np.arange(n_bits)*result.measurements['m'], axis=1)/2**n_bits\n",
        "  \n",
        "  return theta_estimates"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jtqKb_o6oKBF",
        "colab_type": "code",
        "outputId": "14656df8-07d7-4823-c3d1-f0e18edcf65f",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 53
        }
      },
      "source": [
        "phase_estimation(0.234,10)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([0.234375, 0.234375, 0.234375, 0.234375, 0.      , 0.      ,\n",
              "       0.234375, 0.      , 0.234375, 0.234375])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 52
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wzTnTpC2oL79",
        "colab_type": "text"
      },
      "source": [
        "Notice that half of the measurements yielded the estimate $0$, which corresponds to the eigenvaule $1$. If you experiment with different gates and input states you should see the more general behavior.\n",
        "\n",
        "Often we won't be able to prepare an exact eigenstate of the operator $U$ we are interested in, so it's very useful to know about this feature of phase estimation. This is crucial for understanding [Shor's algorithm](https://en.wikipedia.org/wiki/Shor%27s_algorithm), for instance."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zQzAYK-VNVDu",
        "colab_type": "text"
      },
      "source": [
        "### Exercise: Quantum Fourier Transform with Unreversed Output\n",
        "\n",
        "It may be convenient to have an alternative form of the QFT where the output bits are not in the opposite order of the input bits. Can you make an alternative implementation which does that automatically? You may want to consider using SWAP gates."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "EG6cDFWJk-ZS",
        "colab_type": "text"
      },
      "source": [
        "### Exercise: Phase Estimation with Arbitrary $U$\n",
        "\n",
        "Try to implement the phase estimation algorithm in a way that an arbitrary gate $U$ can be supplied and tested. After you've done that, you can test the algorithm on some of your favorite two- or three-qubit gates."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9WKZoaav0dtt",
        "colab_type": "text"
      },
      "source": [
        "### Exercise: QFT and Phase Estimation with Adjacency Constraints\n",
        "\n",
        "Often on a real machine we can't execute two-qubit gates between qubits that are not right next to each other. You'll have noticed that the circuits we defined above involves connections between many different pairs of qubits, which will likely not all be near each other when we try to run the circuit on an actual chip. See if you can modify the examples we went through above in such a way that Cirq validates them for use on the Foxtail or Bristlecone chips. How bit of an example can you handle?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ksA-fvrZaT5g",
        "colab_type": "text"
      },
      "source": [
        "## Grover's Algorithm\n",
        "\n",
        "The Grover algorithm takes a black-box oracle implementing a function\n",
        "$f(x) = 1\\text{ if }x=x',~ f(x) = 0 \\text{ if } x\\neq x'$ and finds $x'$ within a randomly ordered sequence of $N$ items using $O(\\sqrt{N}$) operations and $O(N\\,  \\text{log}N$) gates,\n",
        "with the probability $p \\geq 2/3$.\n",
        "At the moment, only 2-bit sequences (for which one pass through Grover operator\n",
        "is enough) are considered.\n",
        "\n",
        "=== REFERENCE ===\n",
        "\n",
        "Coles, Eidenbenz et al. Quantum Algorithm Implementations for Beginners\n",
        "https://arxiv.org/abs/1804.03719"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gaUMhMV0aaVB",
        "colab_type": "code",
        "outputId": "e86a5e93-73fe-4a4a-b030-ca1eefe3f418",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 215
        }
      },
      "source": [
        "def set_io_qubits(qubit_count):\n",
        "    \"\"\"Add the specified number of input and output qubits.\"\"\"\n",
        "    input_qubits = [cirq.GridQubit(i, 0) for i in range(qubit_count)]\n",
        "    output_qubit = cirq.GridQubit(qubit_count, 0)\n",
        "    return (input_qubits, output_qubit)\n",
        "\n",
        "\n",
        "def make_oracle(input_qubits, output_qubit, x_bits):\n",
        "    \"\"\"Implement function {f(x) = 1 if x==x', f(x) = 0 if x!= x'}.\"\"\"\n",
        "    # Make oracle.\n",
        "    # for (1, 1) it's just a Toffoli gate\n",
        "    # otherwise negate the zero-bits.\n",
        "    yield(cirq.X(q) for (q, bit) in zip(input_qubits, x_bits) if not bit)\n",
        "    yield(cirq.TOFFOLI(input_qubits[0], input_qubits[1], output_qubit))\n",
        "    yield(cirq.X(q) for (q, bit) in zip(input_qubits, x_bits) if not bit)\n",
        "\n",
        "\n",
        "def make_grover_circuit(input_qubits, output_qubit, oracle):\n",
        "    \"\"\"Find the value recognized by the oracle in sqrt(N) attempts.\"\"\"\n",
        "    # For 2 input qubits, that means using Grover operator only once.\n",
        "    c = cirq.Circuit()\n",
        "\n",
        "    # Initialize qubits.\n",
        "    c.append([\n",
        "        cirq.X(output_qubit),\n",
        "        cirq.H(output_qubit),\n",
        "        cirq.H.on_each(*input_qubits),\n",
        "    ])\n",
        "\n",
        "    # Query oracle.\n",
        "    c.append(oracle)\n",
        "\n",
        "    # Construct Grover operator.\n",
        "    c.append(cirq.H.on_each(*input_qubits))\n",
        "    c.append(cirq.X.on_each(*input_qubits))\n",
        "    c.append(cirq.H.on(input_qubits[1]))\n",
        "    c.append(cirq.CNOT(input_qubits[0], input_qubits[1]))\n",
        "    c.append(cirq.H.on(input_qubits[1]))\n",
        "    c.append(cirq.X.on_each(*input_qubits))\n",
        "    c.append(cirq.H.on_each(*input_qubits))\n",
        "\n",
        "    # Measure the result.\n",
        "    c.append(cirq.measure(*input_qubits, key='result'))\n",
        "\n",
        "    return c\n",
        "\n",
        "\n",
        "def bitstring(bits):\n",
        "    return ''.join(str(int(b)) for b in bits)\n",
        "\n",
        "\n",
        "qubit_count = 2\n",
        "circuit_sample_count = 10\n",
        "\n",
        "#Set up input and output qubits.\n",
        "(input_qubits, output_qubit) = set_io_qubits(qubit_count)\n",
        "\n",
        "#Choose the x' and make an oracle which can recognize it.\n",
        "x_bits = [random.randint(0, 1) for _ in range(qubit_count)]\n",
        "print('Secret bit sequence: {}'.format(x_bits))\n",
        "\n",
        "# Make oracle (black box)\n",
        "oracle = make_oracle(input_qubits, output_qubit, x_bits)\n",
        "\n",
        "# Embed the oracle into a quantum circuit implementing Grover's algorithm.\n",
        "circuit = make_grover_circuit(input_qubits, output_qubit, oracle)\n",
        "print('Circuit:')\n",
        "print(circuit)\n",
        "\n",
        "# Sample from the circuit a couple times.\n",
        "simulator = cirq.Simulator()\n",
        "result = simulator.run(circuit, repetitions=circuit_sample_count)\n",
        "\n",
        "frequencies = result.histogram(key='result', fold_func=bitstring)\n",
        "print('Sampled results:\\n{}'.format(frequencies))\n",
        "\n",
        "# Check if we actually found the secret value.\n",
        "most_common_bitstring = frequencies.most_common(1)[0][0]\n",
        "print('Most common bitstring: {}'.format(most_common_bitstring))\n",
        "print('Found a match: {}'.format(\n",
        "    most_common_bitstring == bitstring(x_bits)))\n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Secret bit sequence: [0, 1]\n",
            "Circuit:\n",
            "(0, 0): ───H───X───@───X───H───X───@───X───H───────M('result')───\n",
            "                   │               │               │\n",
            "(1, 0): ───H───────@───H───X───H───X───H───X───H───M─────────────\n",
            "                   │\n",
            "(2, 0): ───X───H───X─────────────────────────────────────────────\n",
            "Sampled results:\n",
            "Counter({'01': 10})\n",
            "Most common bitstring: 01\n",
            "Found a match: True\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}